package Array;

public class lc76 {
    public String minWindow(String s, String t) {
        char[] S = s.toCharArray();
        int m = S.length;
        int ansLeft = -1;
        int ansRight = m;
        int[] cnts = new int[128];
        int[] cntt = new int[128];
        for (char c : t.toCharArray()) {
            cntt[c]++;
        }
        int left = 0;
        for (int right = 0; right < m; right++) {
            cnts[S[right]]++;
            while (isCovered(cnts, cntt)) {
                if (right - left < ansRight - ansLeft) {
                    ansLeft = left;
                    ansRight = right;
                }
                cnts[S[left]]--;
                left++;
            }
        }
        return ansLeft < 0 ? "" : s.substring(ansLeft, ansRight + 1);
    }
    private boolean isCovered(int[] cntS, int[] cntT) {
        for (int i = 'A'; i <= 'Z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        for (int i = 'a'; i <= 'z'; i++) {
            if (cntS[i] < cntT[i]) {
                return false;
            }
        }
        return true;
    }
}